{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Last Stone Weight II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: lastStoneWeightII"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最后一块石头的重量 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一堆石头，用整数数组&nbsp;<code>stones</code> 表示。其中&nbsp;<code>stones[i]</code> 表示第 <code>i</code> 块石头的重量。</p>\n",
    "\n",
    "<p>每一回合，从中选出<strong>任意两块石头</strong>，然后将它们一起粉碎。假设石头的重量分别为&nbsp;<code>x</code> 和&nbsp;<code>y</code>，且&nbsp;<code>x &lt;= y</code>。那么粉碎的可能结果如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果&nbsp;<code>x == y</code>，那么两块石头都会被完全粉碎；</li>\n",
    "\t<li>如果&nbsp;<code>x != y</code>，那么重量为&nbsp;<code>x</code>&nbsp;的石头将会完全粉碎，而重量为&nbsp;<code>y</code>&nbsp;的石头新重量为&nbsp;<code>y-x</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>最后，<strong>最多只会剩下一块 </strong>石头。返回此石头 <strong>最小的可能重量 </strong>。如果没有石头剩下，就返回 <code>0</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>stones = [2,7,4,1,8,1]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>\n",
    "组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，\n",
    "组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，\n",
    "组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，\n",
    "组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>stones = [31,26,33,21,40]\n",
    "<strong>输出：</strong>5\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= stones.length &lt;= 30</code></li>\n",
    "\t<li><code>1 &lt;= stones[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [last-stone-weight-ii](https://leetcode.cn/problems/last-stone-weight-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [last-stone-weight-ii](https://leetcode.cn/problems/last-stone-weight-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,7,4,1,8,1]', '[31,26,33,21,40]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        sums=sum(stones)\n",
    "        target=sums//2\n",
    "        dp=[False]*(target+1)\n",
    "        dp[0]=True\n",
    "        for i in range(len(stones)):\n",
    "            for j in range(target,stones[i]-1,-1):\n",
    "                dp[j]=dp[j] or dp[j-stones[i]]\n",
    "        if dp[target]:\n",
    "            return sums-target-target\n",
    "        for i in range(target,-1,-1):\n",
    "            if dp[i] is True:\n",
    "                return sums-i-i\n",
    "\"\"\"class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        target = sum(stones)/2.0\n",
    "        candidates = {0}\n",
    "        for x in stones:\n",
    "            addition = set()\n",
    "            for y in candidates:\n",
    "                s = x+y\n",
    "                if s==target:\n",
    "                    return 0\n",
    "                elif x+y< target:\n",
    "                    addition.add(s)\n",
    "            candidates = candidates.union(addition)\n",
    "        return int(2*(target-max(candidates)))\"\"\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        total = sum(stones)\n",
    "        num = len(stones)\n",
    "        middle = total // 2\n",
    "        dp = [ [0 for i in range(middle + 1)] for i in range(num)]\n",
    "        \n",
    "        for i in range(num):\n",
    "            for j in range(middle + 1):\n",
    "                if i == 0:\n",
    "                    if j < stones[i]:\n",
    "                        dp[i][j] = 0\n",
    "                    else:\n",
    "                        dp[i][j] = stones[i]\n",
    "                else:\n",
    "                    if j < stones[i]:\n",
    "                        dp[i][j] = dp[i-1][j]\n",
    "                    else:\n",
    "                        dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i]] + stones[i])\n",
    "\n",
    "        res = total - dp[i][j] \n",
    "        diff = abs(res - dp[i][j])\n",
    "        return diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        # n = 30  O(n*sumall)\n",
    "        # 提示 最后剩下的重量总能表示为 \\sum k_i stones[i]  k_i\\in {-1, 1}\n",
    "        # target = positive - neg = sumall - 2*neg\n",
    "        sumall = sum(stones)\n",
    "        n = len(stones)\n",
    "        # 求neg的所有取值情况 变成0,1背包问题\n",
    "        dp = [[False]*(sumall+1) for _ in range(n+1)]  # 前i个元素是否能相加得到j\n",
    "        dp[0][0] = True\n",
    "        for i in range(1, n+1):\n",
    "            for num in range(sumall+1):\n",
    "                dp[i][num] = dp[i-1][num] or (num-stones[i-1] >= 0 and dp[i-1][num-stones[i-1]])\n",
    "        # 最小化target\n",
    "        for num in range(sumall//2, -1, -1):\n",
    "            if dp[n][num]:\n",
    "                return sumall-2*num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        _sum = sum(stones)\n",
    "        target = _sum // 2\n",
    "        dp = [[0] * len(stones) for _ in range(target + 1)]\n",
    "        \n",
    "        for i in range(len(stones)):\n",
    "            for j in range(len(dp)):\n",
    "                if j < stones[i]:\n",
    "                    dp[j][i] = dp[j][i-1]\n",
    "                else:\n",
    "                    dp[j][i] = max(dp[j][i-1], dp[j-stones[i]][i-1] + stones[i])\n",
    "\n",
    "        return _sum - (dp[-1][-1] << 1)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        s = sum(stones)\n",
    "        n,m = len(stones),s//2\n",
    "        dp = [False]*(m+1)\n",
    "        dp[0] = True\n",
    "\n",
    "        for w in stones:\n",
    "            for j in range(m,w-1,-1):\n",
    "                dp[j] |= dp[j-w]\n",
    "        \n",
    "        ans = None\n",
    "\n",
    "        for j in range(m,-1,-1):\n",
    "            if dp[j]:\n",
    "                ans = s-2*j\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones):\n",
    "        total_sum = sum(stones)\n",
    "        target = total_sum // 2\n",
    "        dp = [False] * (target + 1)\n",
    "        dp[0] = True\n",
    "\n",
    "        for stone in stones:\n",
    "            for j in range(target, stone - 1, -1):\n",
    "                # 判断当前重量是否可以通过选择之前的石头得到或选择当前石头和之前的石头得到\n",
    "                dp[j] = dp[j] or dp[j - stone]\n",
    "\n",
    "        for i in range(target, -1, -1):\n",
    "            if dp[i]:\n",
    "                # 返回剩余石头的重量，即总重量减去两倍的最接近总重量一半的重量\n",
    "                return total_sum - 2 * i\n",
    "\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        sum_ = sum(stones)\n",
    "        # if sum_ % 2 == 1: return 0\n",
    "        target = sum_ // 2\n",
    "        dp = [0]*(target+1)\n",
    "        print(target)\n",
    "        for stone in stones:\n",
    "            for j in range(target, stone-1, -1):\n",
    "                dp[j] = max(dp[j], dp[j-stone]+stone)\n",
    "        return sum_ - dp[target] - dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        #第一步建模，转化问题成0-1背包问题\n",
    "        #要想剩下的石头重量最小，则相当于是将石头分成两堆，让两堆石头的重量差越小越好，相当于是挑一堆石头的重量和越接近sum(nums)//2\n",
    "        total = sum(stones)  #因为石头的重量都是介于1到100之间的数\n",
    "        target = total//2\n",
    "        dp=[False for _ in range(target+1)] #dp[j]表示是否存在石头重量和为j\n",
    "        dp[0]=True\n",
    "        True_indx=0\n",
    "        for i in range(len(stones)):\n",
    "            for j in range(target,-1,-1):\n",
    "                tmp=False\n",
    "                if j>=stones[i]:\n",
    "                    tmp = dp[j-stones[i]]\n",
    "                dp[j] = dp[j] or tmp\n",
    "                if dp[j] and j>True_indx:\n",
    "                    True_indx=j\n",
    "        # print(dp,True_indx)\n",
    "        return total - 2*True_indx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        total = sum(stones)\n",
    "        n, m = len(stones), total // 2\n",
    "        dp = [False] * (m + 1)\n",
    "        dp[0] = True\n",
    "\n",
    "        for weight in stones:\n",
    "            for j in range(m, weight - 1, -1):\n",
    "                dp[j] |= dp[j - weight]\n",
    "        \n",
    "        ans = None\n",
    "        for j in range(m, -1, -1):\n",
    "            if dp[j]:\n",
    "                ans = total - 2 * j\n",
    "                break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        s = sum(stones)\n",
    "        t = s // 2\n",
    "        dp = [0 for _ in range(t+1)]\n",
    "        for stone in stones:\n",
    "            for j in range(t, stone-1, -1):\n",
    "                dp[j] = max(dp[j], dp[j-stone] + stone)\n",
    "        return s-2*dp[t]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones):\n",
    "        total_sum = sum(stones)\n",
    "        target = total_sum // 2\n",
    "        dp = [False] * (target + 1)\n",
    "        dp[0] = True\n",
    "\n",
    "        for stone in stones:\n",
    "            for j in range(target,stone - 1,-1):\n",
    "                # 判断当前重量是否可以通过选择之前的石头得到或选择当前石头和之前的石头得到\n",
    "                dp[j] |= dp[j - stone]\n",
    "\n",
    "        for i in range(target,-1,-1):\n",
    "            if dp[i]:\n",
    "                return total_sum - 2 * i\n",
    "        \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        target=sum(stones)//2\n",
    "        dp=[0]*(target+1)\n",
    "        #dp[i]代表容量为i的背包能存放的最大重量\n",
    "        for stone in stones:\n",
    "            for i in range(target,stone-1,-1):\n",
    "                dp[i]=max(dp[i],dp[i-stone]+stone)\n",
    "        return sum(stones)-2*dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        s = sum(stones)\n",
    "        t = s // 2\n",
    "        f = [0] * (t + 1)\n",
    "       \n",
    "        for i in range(n):\n",
    "            for j in range(t, stones[i] - 1, -1):\n",
    "                f[j] = max(f[j - stones[i]] + stones[i], f[j])\n",
    "        return s - f[t] * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        all_stones=0\n",
    "        for i in range(len(stones)):\n",
    "            all_stones+=stones[i]\n",
    "        target=all_stones//2\n",
    "        dp=[0]*3000\n",
    "        for one_stone in stones:\n",
    "            for j in range(target,one_stone-1,-1):\n",
    "                dp[j]=max(dp[j],dp[j-one_stone]+one_stone)\n",
    "        x=dp[target]\n",
    "        y=all_stones-x\n",
    "        return y-x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        dp = [0]*1501\n",
    "        target = sum(stones) // 2\n",
    "        for stone in stones:  # 遍历物品\n",
    "            for i in range(target, stone-1, -1):# 遍历背包\n",
    "                dp[i] = max(dp[i], dp[i-stone]+stone)\n",
    "        return sum(stones) - 2*dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        sum_ = sum(stones)\n",
    "        # if sum_ % 2 == 1: return 0\n",
    "        target = sum_ // 2\n",
    "        dp = [0]*(target+1)\n",
    "        for i in range(len(stones)):\n",
    "            for j in range(target, stones[i]-1, -1):\n",
    "                dp[j] = max(dp[j - stones[i]]+stones[i], dp[j])\n",
    "        print(dp)\n",
    "        return sum_ - dp[target]*2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        total_sum=sum(stones)\n",
    "        half_sum = total_sum//2\n",
    "        n=len(stones)\n",
    "        dp = [0]*(half_sum+1)\n",
    "        for i in range(n):\n",
    "            for j in range(half_sum,-1,-1):\n",
    "                if j>=stones[i]:\n",
    "                    dp[j]=max(dp[j],stones[i]+dp[j-stones[i]])\n",
    "            #print(dp)\n",
    "\n",
    "        return total_sum-dp[-1]-dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        # 将一堆石头分成总重量相近的两堆，两堆的总差值即为所求\n",
    "\n",
    "        # 使用一维数组 dp[j] 记录背包中容量为 j 实际能装的最大重量\n",
    "        target = sum(stones) // 2\n",
    "        dp = [0] * (target+1)\n",
    "\n",
    "        # 递推关系：dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])\n",
    "\n",
    "        # 初始化：dp[0] = 0 赋予一个不会被覆盖的数\n",
    "\n",
    "        # 举例递推\n",
    "        for stone in stones:                    # 遍历物体\n",
    "            for j in range(target,stone-1,-1):  # 遍历背包\n",
    "                dp[j] = max(dp[j], dp[j-stone]+stone)\n",
    "\n",
    "        # 两堆的总差值即为所求\n",
    "        return sum(stones) - dp[target]*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        totalWeight=sum(stones)\n",
    "        target=totalWeight//2\n",
    "        dp=[0]*(target+1)\n",
    "        for stone in stones:\n",
    "            for j in range(target,stone-1,-1):\n",
    "                dp[j]=max(dp[j],dp[j-stone]+stone)\n",
    "        return totalWeight-2*dp[-1]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "#         size = len(stones)\n",
    "#         if size == 1:\n",
    "#             return stones[0]\n",
    "#         sum_target = sum(stones)\n",
    "#         target = sum_target // 2\n",
    "\n",
    "#         dp = [[True] + [False] * target for _ in range(size)]\n",
    "#         dp[0][stones[0]] = True\n",
    "\n",
    "#         for i in range(1, size):\n",
    "#             stone = stones[i]\n",
    "#             for j in range(1, target + 1):\n",
    "#                 if j >= stone:\n",
    "#                     dp[i][j] = dp[i - 1][j] | dp[i - 1][j - stone]\n",
    "#                 else:\n",
    "#                     dp[i][j] = dp[i - 1][j]\n",
    "        \n",
    "#         for max_num in range(target, -1, -1):\n",
    "#             if dp[-1][max_num]:\n",
    "#                 break\n",
    "\n",
    "#         res = abs(sum_target-max_num-max_num)\n",
    "\n",
    "#         return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        size = len(stones)\n",
    "        if size == 1:\n",
    "            return stones[0]\n",
    "        sum_target = sum(stones)\n",
    "        target = sum_target // 2\n",
    "\n",
    "        dp = [True] + [False] * target\n",
    "        \n",
    "\n",
    "        for i in range(size):\n",
    "            stone = stones[i]\n",
    "            for j in range(target, stone - 1, -1):\n",
    "                dp[j] |= dp[j - stone]\n",
    "        \n",
    "        for max_num in range(target, -1, -1):\n",
    "            if dp[max_num]:\n",
    "                break\n",
    "\n",
    "        res = abs(sum_target-max_num-max_num)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        target = sum(stones)//2\n",
    "        dp = [0]*(target+1)\n",
    "        for i in range(len(stones)):\n",
    "            for j in range(target,stones[i]-1,-1):\n",
    "                dp[j] = max(dp[j],dp[j-stones[i]]+stones[i])\n",
    "        return (sum(stones)-dp[-1])-dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        sum = 0\n",
    "        for ele in stones:\n",
    "            sum += ele\n",
    "        target = sum//2\n",
    "        dp = [0] * (target + 1)\n",
    "        for stone in stones:\n",
    "            for content in range(target,stone - 1,-1):\n",
    "                dp[content] = max(dp[content],dp[content-stone] + stone)\n",
    "        res = sum - 2 * dp[target]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        total = sum(stones)\n",
    "        n, m = len(stones), total // 2\n",
    "        dp = [False] * (m + 1)\n",
    "        dp[0] = True\n",
    "\n",
    "        for weight in stones:\n",
    "            for j in range(m, weight - 1, -1):\n",
    "                dp[j] |= dp[j - weight]\n",
    "        \n",
    "        ans = None\n",
    "        for j in range(m, -1, -1):\n",
    "            if dp[j]:\n",
    "                ans = total - 2 * j\n",
    "                break\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "\n",
    "        n = len(stones)\n",
    "\n",
    "        sum = 0\n",
    "        for s in stones:\n",
    "            sum += s\n",
    "\n",
    "        target = sum // 2\n",
    "\n",
    "        dp = [0 for _ in range(target + 1)]\n",
    "\n",
    "        for stone in stones:\n",
    "            for j in range(target, stone-1, -1):\n",
    "                dp[j] = max(dp[j], dp[j-stone]+stone)\n",
    "\n",
    "        return sum - dp[target] - dp[target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        s = sum(stones)\n",
    "        target = s // 2\n",
    "        dp = [0] * (target + 1)\n",
    "        for stone in stones:\n",
    "            for j in range(target, stone - 1, -1):\n",
    "                dp[j] = max(dp[j], dp[j - stone] + stone)\n",
    "        return s - 2 * dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        dp = [0] * 2000\n",
    "        sum1 = sum(stones)\n",
    "        \n",
    "        target = sum1 // 2\n",
    "        for i in range(0, len(stones)):\n",
    "            for j in range(target, stones[i] - 1, -1):\n",
    "                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])\n",
    "        \n",
    "        return sum1 - dp[target] - dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        target = int(sum(stones)/2)\n",
    "        dp = [0 for _ in range(target+1)]\n",
    "        for i in range(len(stones)):\n",
    "          for j in range(target, stones[i]-1, -1):\n",
    "              dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])\n",
    "        return sum(stones)-2 * dp[target]      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        total = sum(stones)\n",
    "        target = total // 2\n",
    "        dp = [0] * (target + 1)\n",
    "        for stone in stones:\n",
    "            for j in range(target, stone-1, -1):\n",
    "                dp[j] = max(dp[j], dp[j-stone] + stone)\n",
    "        return total - dp[target] - dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "\n",
    "        n = len(stones)\n",
    "\n",
    "        sum = 0\n",
    "        for s in stones:\n",
    "            sum += s\n",
    "\n",
    "        target = sum // 2\n",
    "\n",
    "        dp = [0 for _ in range(target + 1)]\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(target, stones[i-1]-1, -1):\n",
    "                dp[j] = max(dp[j], dp[j-stones[i-1]]+stones[i-1])\n",
    "\n",
    "        return sum - dp[target] - dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: list[int]) -> int:\n",
    "        sums = sum(stones)\n",
    "        m = len(stones)\n",
    "        n = sums // 2\n",
    "        dp = [0 for _ in range(n+1)]\n",
    "        for item in range(m):\n",
    "            for capacity in range(n, stones[item]-1, -1):\n",
    "                # if capacity - stones[item] >= 0:\n",
    "                    dp[capacity] = max(dp[capacity], dp[capacity-stones[item]]+stones[item])\n",
    "        # Test.Test().printDp1(dp)\n",
    "        return abs(dp[n] - (sums - dp[n]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        total_sum = sum(stones)\n",
    "        target = total_sum // 2\n",
    "        dp = [[False] * (target+1) for _ in range(len(stones) +1)]\n",
    "        for i in range(len(stones) +1):\n",
    "            dp[i][0] = True\n",
    "        for i in range(1,len(stones) +1 ):\n",
    "            for j in range(1,target+1):\n",
    "                if stones[i-1] > j:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i - 1][j] or dp[i - 1][j - stones[i - 1]]\n",
    "        for i in range(target, -1, -1):\n",
    "            if dp[len(stones)][i]:\n",
    "                return total_sum - 2 * i\n",
    "        \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        dp = [0] * 15001\n",
    "        total_sum = sum(stones)\n",
    "        target = total_sum // 2\n",
    "\n",
    "        for stone in stones:  # 遍历物品\n",
    "            for j in range(target, stone - 1, -1):  # 遍历背包\n",
    "                dp[j] = max(dp[j], dp[j - stone] + stone)\n",
    "\n",
    "        return total_sum - dp[target] - dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        total = sum(stones)\n",
    "        n, m = len(stones), total // 2\n",
    "        dp = [[False] * (m + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = True\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m + 1):\n",
    "                if j < stones[i]:\n",
    "                    dp[i + 1][j] = dp[i][j]\n",
    "                else:\n",
    "                    dp[i + 1][j] = dp[i][j] or dp[i][j - stones[i]]\n",
    "        \n",
    "        ans = None\n",
    "        for j in range(m, -1, -1):\n",
    "            if dp[n][j]:\n",
    "                ans = total - 2 * j\n",
    "                break\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        total = sum(stones)\n",
    "        n, m = len(stones), total // 2\n",
    "        dp = [[False] * (m + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = True\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m + 1):\n",
    "                if j < stones[i]:\n",
    "                    dp[i + 1][j] = dp[i][j]\n",
    "                else:\n",
    "                    dp[i + 1][j] = dp[i][j] or dp[i][j - stones[i]]\n",
    "        \n",
    "        ans = None\n",
    "        for j in range(m, -1, -1):\n",
    "            if dp[n][j]:\n",
    "                ans = total - 2 * j\n",
    "                break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "\n",
    "        total = sum(stones)\n",
    "        target = total // 2\n",
    "        dp = [[0] * (target + 1) for _ in range(len(stones) + 1)]\n",
    "\n",
    "        for i in range(len(stones) + 1):\n",
    "            dp[i][0] = True\n",
    "\n",
    "        for i in range(1, len(stones) + 1):\n",
    "            for j in range(target + 1):\n",
    "                if stones[i - 1] > j:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i - 1][j] or dp[i - 1][j - stones[i - 1]]\n",
    "\n",
    "        for i in range(target, -1, -1):\n",
    "            if dp[len(stones)][i]:\n",
    "                return total - 2 * i\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        size = len(stones)\n",
    "        if size == 1:\n",
    "            return stones[0]\n",
    "        sum_target = sum(stones)\n",
    "        target = sum_target // 2\n",
    "\n",
    "        dp = [[True] + [False] * target for _ in range(size)]\n",
    "        dp[0][stones[0]] = True\n",
    "\n",
    "        for i in range(1, size):\n",
    "            stone = stones[i]\n",
    "            for j in range(1, target + 1):\n",
    "                if j >= stone:\n",
    "                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - stone]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "        \n",
    "        for max_num in range(target, -1, -1):\n",
    "            if dp[-1][max_num]:\n",
    "                break\n",
    "\n",
    "        res = abs(sum_target-max_num-max_num)\n",
    "\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        sum_stones = sum(stones)\n",
    "        target = sum_stones // 2\n",
    "        dp = [[0] * (target + 1) for _ in range(len(stones))]\n",
    "\n",
    "        for j in range(stones[0], target+1):\n",
    "            dp[0][j] = stones[0]\n",
    "\n",
    "        for i in range(len(stones)):\n",
    "            for j in range(target+1):\n",
    "                if j < stones[i]:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i]]+stones[i])\n",
    "        print('dp', dp[-1][-1])\n",
    "        return sum_stones - dp[-1][-1] - dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        total = sum(stones)\n",
    "        m = total // 2 + 1\n",
    "        dp = [[False for _ in range(m)] for _ in range(len(stones)+1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(1, len(stones)+1):\n",
    "            for j in range(m):\n",
    "                if j < stones[i-1]:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j] or dp[i-1][j-stones[i-1]]\n",
    "        ans = None\n",
    "        # print(dp, m)\n",
    "        for i in range(m-1, -1, -1):\n",
    "            if dp[-1][i]:\n",
    "                # print(total, i)\n",
    "                ans = total - 2 * i\n",
    "                # print(ans)\n",
    "            if ans is not None:\n",
    "                break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        total = sum(stones)\n",
    "        n = len(stones)\n",
    "        m = total // 2\n",
    "        dp = [[False] * (m+1) for _ in range(n+1)]\n",
    "        dp[0][0] = True \n",
    "        for i in range(n):\n",
    "            for j in range(m+1):\n",
    "                if j < stones[i]:\n",
    "                    dp[i+1][j] = dp[i][j]\n",
    "                else:\n",
    "                    dp[i+1][j] = dp[i][j] or dp[i][j-stones[i]]\n",
    "        res = None\n",
    "        for j in range(m, -1, -1):\n",
    "            if dp[n][j]:\n",
    "                res = total - 2 * j\n",
    "                break\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # total = sum(stones)\n",
    "        # n, m = len(stones), total // 2\n",
    "        # dp = [False] * (m+1)\n",
    "        # dp[0] = True\n",
    "        # for i in range(n):\n",
    "        #     for j in range(m, -1, -1):\n",
    "        #         if stones[i] <= j:\n",
    "        #             dp[j] = dp[j] or dp[j-stones[i]]\n",
    "        # res = None \n",
    "        # for j in range(m, -1, -1):\n",
    "        #     if dp[j]:\n",
    "        #         res = total - 2*j\n",
    "        #         break\n",
    "        # return res\n",
    "\n",
    "        # total = sum(stones)\n",
    "        # n = len(stones)\n",
    "        # m = total // 2\n",
    "        # dp = [[False] * (m+1) for _ in range(n+1)]\n",
    "        # dp[0][0] = True \n",
    "        # for i in range(n):\n",
    "        #     for j in range(m+1):\n",
    "        #         if stones[i] > j:\n",
    "        #             dp[i+1][j] = dp[i][j]\n",
    "        #         else:\n",
    "        #             dp[i+1][j] = dp[i][j] or dp[i][j-stones[i]]\n",
    "        # res = None \n",
    "        # for j in range(m, -1, -1):\n",
    "        #     if dp[n][j]:\n",
    "        #         res = total - 2 * j\n",
    "        #         break\n",
    "        # return res\n",
    "\n",
    "\n",
    "        # total = sum(stones)\n",
    "        # n, m = len(stones), total // 2\n",
    "        # dp = [False] * (m + 1)\n",
    "        # dp[0] = True\n",
    "\n",
    "        # for weight in stones:\n",
    "        #     for j in range(m, weight - 1, -1):\n",
    "        #         dp[j] |= dp[j - weight]\n",
    "        \n",
    "        # ans = None\n",
    "        # for j in range(m, -1, -1):\n",
    "        #     if dp[j]:\n",
    "        #         ans = total - 2 * j\n",
    "        #         break\n",
    "        \n",
    "        # return ans\n",
    "\n",
    "\n",
    "        # total = sum(stones)\n",
    "        # n, m = len(stones), total // 2\n",
    "        # dp = [[False] * (m+1) for _ in range(n+1)]\n",
    "        # dp[0][0] = True\n",
    "        # for i in range(n):\n",
    "        #     for j in range(m+1):\n",
    "        #         if j < stones[i]:\n",
    "        #             dp[i+1][j] = dp[i][j]\n",
    "        #         else:\n",
    "        #             dp[i+1][j] = dp[i][j] or dp[i][j-stones[i]]\n",
    "        # res = None\n",
    "        # for j in range(m, -1, -1):\n",
    "        #     if dp[n][j]:\n",
    "        #         res = total - 2 * j\n",
    "        #         break\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        total = sum(stones)\n",
    "        n, m = len(stones), total // 2\n",
    "        dp = [[False] * (m + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = True\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m + 1):\n",
    "                if j < stones[i]:\n",
    "                    dp[i + 1][j] = dp[i][j]\n",
    "                else:\n",
    "                    dp[i + 1][j] = dp[i][j] or dp[i][j - stones[i]]\n",
    "        \n",
    "        ans = None\n",
    "        for j in range(m, -1, -1):\n",
    "            if dp[n][j]:\n",
    "                ans = total - 2 * j\n",
    "                break\n",
    "        \n",
    "        return ans\n",
    "        # total = sum(stones)\n",
    "        # target = total // 2\n",
    "        # dp = [[False] * (target + 1) for _ in range(len(stones)+1)]\n",
    "        # for i in range(len(stones)):\n",
    "        #     dp[i][0] = True\n",
    "\n",
    "        # for i in range(1, len(stones)+1):\n",
    "        #     for j in range(1, target+1):\n",
    "        #         if j < stones[i-1]:\n",
    "        #             dp[i][j] = dp[i-1][j]\n",
    "        #         # dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i-1]] + stones[i-1])\n",
    "        #         dp[i][j] = dp[i-1][j] or dp[i-1][j-stones[i-1]]\n",
    "        # for i in range(target, -1, -1):\n",
    "        #     if dp[len(stones)][i]:\n",
    "        #         return total - 2 * i\n",
    "              \n",
    "        # return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        target = sum(stones) // 2\n",
    "\n",
    "        dp = [[False] * (target + 1) for _ in range(len(stones) + 1)]\n",
    "\n",
    "        for i in range(len(stones) + 1):\n",
    "            dp[i][0] = True\n",
    "        \n",
    "        for i in range(1, len(stones) + 1):\n",
    "            for j in range(1, target + 1):\n",
    "                if j < stones[i-1]:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j] or dp[i-1][j-stones[i-1]]\n",
    "        for i in range(target, -1, -1):\n",
    "            if dp[len(stones)][i]:\n",
    "                return sum(stones) - 2*i\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        su=sum(stones)\n",
    "        m=len(stones)\n",
    "        dp=[[False for j in range(su//2+1)] for i in range(m+1)]\n",
    "        dp[0][0]=True\n",
    "        for i in range(m):\n",
    "            for j in range(su//2+1):\n",
    "                if j<stones[i]:\n",
    "                    dp[i+1][j]=dp[i][j]\n",
    "                else:\n",
    "                    dp[i+1][j]=dp[i][j] or dp[i][j-stones[i]]\n",
    "        res=None\n",
    "        for j in range(su//2,-1,-1):\n",
    "            if dp[m][j]:\n",
    "                res=su-2*j\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        target = sum(stones)\n",
    "        add = target//2\n",
    "        n = len(stones)\n",
    "        dp = [[0]*(add+1) for _ in range(n)]\n",
    "        for i in range(stones[0], add+1):\n",
    "            dp[0][i] = stones[0]\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            for j in range(0, add+1):\n",
    "                if j >= stones[i]:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i]]+stones[i])\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        return abs(target-2*dp[-1][-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        stones=sorted(stones)\n",
    "        weights=stones[:]\n",
    "        weights.insert(0,0)\n",
    "        values=stones[:]\n",
    "        values.insert(0,0)\n",
    "        #print(stones)\n",
    "        \n",
    "        half_sum = sum(stones)//2\n",
    "        dp = [ [0] * (len(stones)+1) for _ in range(half_sum+1) ]\n",
    "        for i in range(1,half_sum+1):\n",
    "            if i>=weights[1]:\n",
    "                dp[i][1]=weights[1]\n",
    "        #print(dp)\n",
    "        for i in range(1,half_sum+1):\n",
    "            for j in range(1,len(stones)+1):\n",
    "                if i>=weights[j]:\n",
    "                    dp[i][j]=max(dp[i][j-1],dp[i-1][j],values[j]+dp[i-weights[j]][j-1])\n",
    "                else:\n",
    "                    dp[i][j]=max( dp[i][j-1], dp[i-1][j] )\n",
    "           \n",
    "            print(dp[i])\n",
    "\n",
    "        min_val = max(dp[-1])\n",
    "        return sum(stones)-min_val-min_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        target = sum(stones) // 2\n",
    "        n = len(stones)\n",
    "        dp = [[0] * (target + 1) for _ in range(n + 1)]\n",
    "        for i in range(1,n + 1):\n",
    "            for j in range(1,target + 1):\n",
    "                if j < stones[i - 1]:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i - 1][j] , dp[i - 1][j - stones[i-1]] + stones[i-1])\n",
    "        return sum(stones) - 2 * dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        if sum(stones) % 2 == 1:\n",
    "            target = int((sum(stones)+1)/2)\n",
    "        else:\n",
    "            target = int(sum(stones)/2)\n",
    "        dp = [[0 for _ in range(target+1)] for _ in range(len(stones))]\n",
    "        for i in range(len(stones)):\n",
    "            for j in range(target+1):\n",
    "                if i == 0:\n",
    "                    if j >= stones[i]:\n",
    "                        dp[i][j] = stones[i]\n",
    "                elif j < stones[i]:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-stones[i]]+stones[i])\n",
    "        return abs(sum(stones)-2*dp[-1][-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        total = 0\n",
    "        for x in stones:\n",
    "            total += x\n",
    "\n",
    "        target = total // 2\n",
    "        dp = [[0]*(target+1) for _ in range(len(stones))]\n",
    "        \n",
    "        # 第一列\n",
    "        for i in range(1, len(stones)):\n",
    "            dp[i][0] = 0\n",
    "\n",
    "        # 第一行\n",
    "        for j in range(1, target+1):\n",
    "            if j >= stones[0]:\n",
    "                dp[0][j] = stones[0]\n",
    "\n",
    "        for i in range(1, len(stones)):\n",
    "            for j in range(1, target+1):\n",
    "                if j >= stones[i]:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i]]+stones[i])\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        another = total - dp[-1][-1]\n",
    "        return total - 2*dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones) :\n",
    "        sum1 = sum(stones)\n",
    "        target = sum1 // 2  # 背包容量\n",
    "        bagsize=target\n",
    "        weight = stones\n",
    "        value = stones\n",
    "        dp=[[0 for _ in range(target+1)] for _ in range(len(weight))]\n",
    "        for j in range(weight[0], bagsize + 1):\n",
    "            dp[0][j] = value[0]\n",
    "        for i in range(1, len(weight)):\n",
    "            for j in range(bagsize + 1):\n",
    "                if j < weight[i]:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])\n",
    "        \n",
    "        return abs(sum1-2*dp[-1][-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        sum_ = sum(stones)\n",
    "        tar = sum_ // 2\n",
    "        dp = [[]] * len(stones)\n",
    "        for row in range(len(dp)):\n",
    "            dp[row] = [0] * (tar + 1)\n",
    "        for col in range(1, tar + 1):\n",
    "            if col >= stones[0]:\n",
    "                dp[0][col] = stones[0]\n",
    "        for row in range(1, len(stones)):\n",
    "            for col in range(1, tar + 1):\n",
    "                if stones[row] > col:\n",
    "                    dp[row][col] = dp[row - 1][col]\n",
    "                else:\n",
    "                    dp[row][col] = max([dp[row - 1][col], dp[row - 1][col - stones[row]] + stones[row]])\n",
    "        return (sum_ - dp[-1][-1]) - dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "\n",
    "        total = sum(stones)//2\n",
    "        dp = [[0] * (total + 1) for _ in range(len(stones))]\n",
    "        res = 0\n",
    "        for i in range(len(stones)):\n",
    "            for j in range(total+1):\n",
    "                if i==0 and j==0:\n",
    "                    dp[i][j] = 0\n",
    "                elif i==0:\n",
    "                    if j>=stones[i]:\n",
    "                        dp[i][j] = stones[i]\n",
    "                elif j==0:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    if j < stones[i]:\n",
    "                        dp[i][j] = dp[i-1][j]\n",
    "                    else:\n",
    "                        dp[i][j] = max(dp[i-1][j],dp[i-1][j-stones[i]]+stones[i])\n",
    "                res = max(res, dp[i][j])\n",
    "        return sum(stones)-res-res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        # dp[i][j] weight j \n",
    "        stones_sum = sum(stones)\n",
    "        nums = len(stones)\n",
    "        max_weight = int(stones_sum / 2) +1\n",
    "        dp = [[0] * max_weight for _ in range(nums)]\n",
    "        dp[0][0] = 0\n",
    "        for i in range(max_weight):\n",
    "            if i < stones[0]:\n",
    "                continue\n",
    "            dp[0][i] = stones[0]\n",
    "        for i in range(1,nums):\n",
    "            for j in range(1, max_weight):\n",
    "                if stones[i] > j:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-stones[i]]+stones[i])\n",
    "        return stones_sum-dp[nums-1][max_weight-1]-dp[nums-1][max_weight-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        stones.sort()\n",
    "        print(stones)\n",
    "        SUM=sum(stones)\n",
    "        n=len(stones)\n",
    "        Target=SUM//2\n",
    "        dp=[[0 for i in range(Target+1)] for j in range(n+1)]\n",
    "        for i in range(n+1):\n",
    "            for j in range(Target+1):\n",
    "                if i==0 or j==0:\n",
    "                    dp[i][j]==0\n",
    "                else:\n",
    "                    if j-stones[i-1]<0:\n",
    "                        dp[i][j]=dp[i-1][j]\n",
    "                    else:\n",
    "                        dp[i][j]=max(dp[i-1][j],dp[i-1][j-stones[i-1]]+stones[i-1])\n",
    "        # for i in dp:\n",
    "        #     print(i)\n",
    "        return abs(SUM-2*dp[n][Target])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        lth=len(stones)\n",
    "        tar=sum(stones)//2\n",
    "        dp=[[0]*(tar+1) for i in range(lth)]\n",
    "        for i in range(tar,-1,-1):\n",
    "            if i>=stones[0]:\n",
    "                dp[0][i]=stones[0]\n",
    "        for i in range(1,lth):\n",
    "            for j in range(tar,-1,-1):\n",
    "                if j>=stones[i]:\n",
    "                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-stones[i]]+stones[i])\n",
    "                    dp[i][j]=max(dp[i][j],stones[i])\n",
    "                else:\n",
    "                    dp[i][j]=dp[i-1][j]\n",
    "        return sum(stones)-2*dp[lth-1][tar]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        ss=sum(stones)//2\n",
    "        dp=[[0]* (ss+1) for _ in range(len(stones))]\n",
    "\n",
    "        for i in range(len(stones)):\n",
    "            for j in range(ss+1):\n",
    "                if i==0 and j>=stones[i]:\n",
    "                    dp[i][j]=stones[i]\n",
    "                else:\n",
    "                    if j>=stones[i]:\n",
    "                        dp[i][j]= max(dp[i-1][j],dp[i-1][j-stones[i]]+stones[i])\n",
    "                    else:\n",
    "                        dp[i][j]=dp[i-1][j]\n",
    "        \n",
    "        x=dp[-1][-1]\n",
    "        return sum(stones)-2*x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        total = 0\n",
    "        for x in stones:\n",
    "            total += x\n",
    "\n",
    "        # 向下取整  target <= 一半\n",
    "        target = total // 2\n",
    "        # dp[i][j]: [0, i]之间任取  最大重量是j 表示的最大价值\n",
    "        dp = [[0]*(target+1) for _ in range(len(stones))]\n",
    "        \n",
    "        # 第一列\n",
    "        for i in range(1, len(stones)):\n",
    "            dp[i][0] = 0\n",
    "\n",
    "        # 第一行\n",
    "        for j in range(1, target+1):\n",
    "            if j >= stones[0]:\n",
    "                dp[0][j] = stones[0]\n",
    "\n",
    "        for i in range(1, len(stones)):\n",
    "            for j in range(1, target+1):\n",
    "                if j >= stones[i]:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i]]+stones[i])\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        another = total - dp[-1][-1]\n",
    "        return total - 2*dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        # 求剩余石头的最小重量，可以转换为取i个石头，使其和最接近sum(stones)//2，\n",
    "        sumV = sum(stones)\n",
    "        target = sumV // 2\n",
    "        n = len(stones)\n",
    "        dp = [[0] * (target + 1) for _ in range(n + 1)]\n",
    "        # dp[i][j] 表示：从输入数组的前缀区间 [0..i] 里取出一部分元素，并且和小于等于 j 的最大值\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(target + 1):\n",
    "                dp[i][j] = dp[i - 1][j]\n",
    "                if stones[i - 1] <= j:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i-1])\n",
    "\n",
    "        # print(dp)\n",
    "        return sumV - 2 * dp[n][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        sum_ = sum(stones)\n",
    "        target = sum_ // 2\n",
    "        dp = [[0]*(target+1) for _ in range(len(stones)+1)]\n",
    "\n",
    "        # for j in range(target+1):\n",
    "        #     if nums[0] <= j:\n",
    "        #         dp[0][j] = nums[0]\n",
    "\n",
    "        for i in range(1, len(stones)+1):\n",
    "            for j in range(1, target+1):\n",
    "                if j < stones[i-1]:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i-1]]+stones[i-1])\n",
    "\n",
    "        # print(dp)\n",
    "        max_weight1 = dp[-1][-1]\n",
    "        max_weight2 = sum_ - max_weight1\n",
    "\n",
    "        return max_weight2-max_weight1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        stones_sum = sum(stones)//2\n",
    "        dp = [[0 for j in range(stones_sum+1)] for i in range(len(stones))]\n",
    "        for j in range(stones_sum+1):\n",
    "            if stones[0]<=j:\n",
    "                dp[0][j] = stones[0]\n",
    "        for i in range(1, len(stones)):\n",
    "            dp[i] = dp[i-1][:]\n",
    "            for j in range(stones[i], stones_sum+1):\n",
    "                dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i]]+stones[i])\n",
    "        return sum(stones)-2*dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        stones=sorted(stones)\n",
    "        weights=stones[:]\n",
    "        weights.insert(0,0)\n",
    "        values=stones[:]\n",
    "        values.insert(0,0)\n",
    "        #print(stones)\n",
    "        \n",
    "        half_sum = sum(stones)//2\n",
    "        dp = [ [0] * (len(stones)+1) for _ in range(half_sum+1) ]\n",
    "        for i in range(1,half_sum+1):\n",
    "            if i>=weights[1]:\n",
    "                dp[i][1]=weights[1]\n",
    "        #print(dp)\n",
    "        for i in range(1,half_sum+1):\n",
    "            for j in range(1,len(stones)+1):\n",
    "                if i>=weights[j]:\n",
    "                    dp[i][j]=max(dp[i][j-1],values[j]+dp[i-weights[j]][j-1])\n",
    "                else:\n",
    "                    dp[i][j]=dp[i][j-1] \n",
    "           \n",
    "            #print(dp[i])\n",
    "\n",
    "        return sum(stones)-dp[-1][-1]-dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        sumStone = sum(stones)\n",
    "        target = sumStone // 2\n",
    "        lenStone = len(stones)\n",
    "        dp = [[0] * (lenStone + 1) for _ in range(target + 1)]\n",
    "        for i in range(1, target + 1):\n",
    "            for j in range(1, lenStone + 1):\n",
    "                if i - stones[j - 1] >= 0:\n",
    "                    dp[i][j] = max(dp[i][j - 1], dp[i - stones[j - 1]][j - 1] + stones[j - 1])\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j - 1]\n",
    "        return sumStone - 2 * dp[target][lenStone]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        volumn = int(sum(stones) / 2)\n",
    "        dp = [[0] * (volumn + 1) for _ in range(len(stones) + 1)]\n",
    "\n",
    "        for i in range(1, len(stones) + 1):\n",
    "            for j in range(1, volumn + 1):\n",
    "                if j < stones[i-1]:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stones[i-1]] + stones[i-1])\n",
    "\n",
    "        return(sum(stones) - 2 * dp[len(stones)][volumn])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        total = sum(stones)\n",
    "        target = total // 2\n",
    "        n = len(stones)\n",
    "        dp = [[0] * (total + 1) for _ in range(n)]\n",
    "        for j in range(stones[0], target + 1):\n",
    "            dp[0][j] = stones[0]\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, target + 1):\n",
    "                if j < stones[i]:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i])\n",
    "        return total - dp[n - 1][target] - dp[n - 1][target]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        if len(stones) == 2:\n",
    "            return abs(stones[0]-stones[1])\n",
    "\n",
    "        rows = len(stones)\n",
    "        cols = sum(stones) // 2 + 1\n",
    "\n",
    "        dp = [[0] * cols for _ in range(rows)]\n",
    "\n",
    "        for col in range(cols):\n",
    "            if col >= stones[0]:\n",
    "                dp[0][col] = stones[0]\n",
    "\n",
    "        for row in range(1, rows):\n",
    "            for col in range(1, cols):\n",
    "                if col >= stones[row]:\n",
    "                    dp[row][col] = max(\n",
    "                        dp[row-1][col],\n",
    "                        dp[row-1][col - stones[row]] + stones[row]\n",
    "                    )\n",
    "                else:\n",
    "                    dp[row][col] = dp[row-1][col]    \n",
    "        print(dp[-1], sum(stones)) \n",
    "        return abs(sum(stones) - dp[-1][-1] * 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        nums_sum = sum(stones)\n",
    "        target = nums_sum/2\n",
    "        dp=[[0 for j in range(nums_sum+1)] for i in range(len(stones))]\n",
    "        for i in range(nums_sum+1):\n",
    "            if i<stones[0]:\n",
    "                dp[0][i] = 0\n",
    "            else:\n",
    "                dp[0][i] = stones[0]\n",
    "\n",
    "        for i in range(1,len(stones)):\n",
    "            for j in range(nums_sum+1):\n",
    "                if j < stones[i]:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-stones[i]]+stones[i])\n",
    "        # print(dp)\n",
    "        return abs(nums_sum - 2 * dp[len(stones)-1][int(target)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        length = len(stones)\n",
    "        results = [{} for i in range(length)]\n",
    "        for i in range(length):\n",
    "            if i == 0:\n",
    "                if stones[i] == 0:\n",
    "                    results[i][stones[i]] = 2\n",
    "                else:\n",
    "                    results[i][stones[i]] = 1\n",
    "                    results[i][-stones[i]] = 1\n",
    "\n",
    "            else:\n",
    "                keys_ = results[i - 1].keys()\n",
    "                keys = results[i].keys()\n",
    "                for k in keys_:\n",
    "                    if (k - stones[i]) in keys:\n",
    "                        results[i][k - stones[i]] = results[i][k - stones[i]] + results[i - 1][k]\n",
    "                    else:\n",
    "                        results[i][k - stones[i]] = results[i - 1][k]\n",
    "\n",
    "                    if (k + stones[i]) in keys:\n",
    "                        results[i][k + stones[i]] = results[i][k + stones[i]] + results[i - 1][k]\n",
    "                    else:\n",
    "                        results[i][k + stones[i]] = results[i - 1][k]\n",
    "\n",
    "        min_ = 1000000\n",
    "        for v in results[-1].keys():\n",
    "            if v >= 0:\n",
    "                min_ = min(min_, v)\n",
    "        return min_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#1049. 最后一块石头的重量 II\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones):\n",
    "        s = sum(stones)//2\n",
    "        l = len(stones)\n",
    "        dp = [[0]*(s+1) for i in range(l+1)]\n",
    "        print(dp)\n",
    "        for i in range(1,l+1):\n",
    "            for j in range(s+1):\n",
    "                if(j<stones[i-1]):\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-stones[i-1]]+stones[i-1])\n",
    "        x = (dp[-1][-1])\n",
    "        return (sum(stones)-2*x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        W = sum(stones)\n",
    "        dp = [[0]*(W+1) for _ in range(n+1)]\n",
    "        target = W//2\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,W+1):\n",
    "                if stones[i-1]>j:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-stones[i-1]]+stones[i-1])\n",
    "        return W-dp[-1][target]-dp[-1][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 相当于给数组元素加正号、负号。令所有加负号的元素的集合是subset，则有正号元素集合是 stones - subset\n",
    "# 那么 结果  = sum(stones) - sum(subset) - sum(subset)\n",
    "# 且要求 sum(stones) - sum(subset) >= sum(subset)\n",
    "# 所以 subset 的总和越大越好，但是不能超过 1/2 * sum(stones)\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        \n",
    "        # 这个过程就是《剑指offer专项版》的subsetSum\n",
    "        @cache\n",
    "        def dfs(i, target):\n",
    "            if i == n:\n",
    "                return int(target == 0)\n",
    "            return dfs(i + 1, target) or stones[i] <= target and dfs(i + 1, target - stones[i])\n",
    "        \n",
    "        s = sum(stones)\n",
    "        for i in range(s // 2, -1, -1):\n",
    "            if dfs(0, i):\n",
    "                return s - 2 * i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "    \n",
    "        n = len(stones)\n",
    "        sum_weight = sum(stones)\n",
    "        target = sum_weight // 2\n",
    "        \n",
    "        # 初始化 dp 数组\n",
    "        # dp[i][j] 表示当只剩下前 i 个石头，且它们的总重量为 j 时，最后剩下的石头的最小可能重量。\n",
    "        dp = [[0] * (target + 1) for _ in range(n + 1)]\n",
    "        print(dp)\n",
    "        \n",
    "        # 状态转移\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(target + 1):\n",
    "                if j >= stones[i-1]:\n",
    "                    dp[i][j] = max(dp[i-1][j-stones[i-1]] + stones[i-1], dp[i-1][j])\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        \n",
    "        print(dp)\n",
    "        # 计算最终答案\n",
    "        return sum_weight - 2 * dp[n][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        import math\n",
    "        # 任选两块时候做差\n",
    "        # 返回最后的差值\n",
    "        # B: 有一定思路，但不一定能做出来\n",
    "        # 核心：让当前结果尽可能接近中心值，回溯，返回最接近的结果\n",
    "        \n",
    "        # 结束条件：\n",
    "        # 》= target // 2\n",
    "        # 待选择：\n",
    "        # 未选择的stone\n",
    "        # 已选择\n",
    "        # 已选择stone\n",
    "        # 子集选择\n",
    "        # 78/90\n",
    "        def back_tracking(start_index,tmp_sum,target,stones,memo):\n",
    "            key = str(start_index) + \"_\" + str(tmp_sum)\n",
    "            if key in memo:\n",
    "                return memo[key]\n",
    "            else:\n",
    "                memo[key] = 1\n",
    "            # target // 2非整数时可能会导致问题\n",
    "            nonlocal min_weight\n",
    "            if tmp_sum >= target // 2:\n",
    "                remain_weight = abs(tmp_sum - (target-tmp_sum))\n",
    "                if remain_weight < min_weight:\n",
    "                    min_weight = remain_weight\n",
    "                return \n",
    "            for index in range(start_index,len(stones)):\n",
    "                tmp_sum += stones[index]\n",
    "                back_tracking(index+1,tmp_sum,target,stones,memo)\n",
    "                tmp_sum -= stones[index]\n",
    "\n",
    "        min_weight = 10000\n",
    "        target = sum(stones)\n",
    "        memo = {}\n",
    "        back_tracking(0,0,target,stones,memo)   \n",
    "        return min_weight"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        B, n = 3005, len(stones)\n",
    "        dp = [[0 for i in range(B*2)] for j in range(n+1)]\n",
    "        dp[0][B] = 1\n",
    "        for k, s in enumerate(stones):\n",
    "            i = k+1\n",
    "            for j in range(2*B):\n",
    "                if j >= s: dp[i][j] += dp[i-1][j-s]\n",
    "                if j+s < 2*B: dp[i][j] += dp[i-1][j+s]\n",
    "            # print(s, dp[i][B-9:B], dp[i][B:B+9])\n",
    "\n",
    "        out = 0\n",
    "        while out+B < 2*B and dp[-1][out+B] == 0: \n",
    "            out += 1\n",
    "        return out\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        m = len(stones)\n",
    "        if m==1: return stones[0]\n",
    "        s = sum(stones)\n",
    "        n = s//2\n",
    "        dp = [[0 for i in range(n+1)] for j in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(n+1):\n",
    "                if j>=stones[i-1]:\n",
    "                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-stones[i-1]]+stones[i-1])\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        print(dp)\n",
    "        return s-2*dp[m][-1]\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        # dp[i][j] : 重量上限为j时 在 0-i物品中能装载物品重量的最大值\n",
    "        # # ???"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        def cal(temp,i,nums,res):\n",
    "            res.append(temp)\n",
    "            for j in range(i,len(nums)):\n",
    "                cal(temp+nums[j],j+1,nums,res)\n",
    "            return res\n",
    "        n=len(stones)\n",
    "        sums=sum(stones)\n",
    "        target=sums//2\n",
    "        c1=cal(0,0,stones[:n//2],[])\n",
    "        c2=cal(0,0,stones[n//2:],[])\n",
    "        c1.sort()\n",
    "        c2.sort()\n",
    "        n1,n2=len(c1),len(c2)\n",
    "        i,j=0,n2-1\n",
    "        diff=float('inf')\n",
    "        while i<n1 and j>-1:\n",
    "            c=c1[i]+c2[j]\n",
    "            if abs(c-target)<abs(diff):\n",
    "                diff=c-target\n",
    "            if c>target:\n",
    "                j-=1\n",
    "            elif c<target:\n",
    "                i+=1\n",
    "            else:\n",
    "                break\n",
    "        return abs(sums-2*target-2*diff)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        # sum_values = sum(stones)\n",
    "        # target = sum_values // 2\n",
    "        # dp = [0] * (target+1)\n",
    "        # for i in range(len(stones)):\n",
    "        #     for j in range(target, stones[i]-1, -1):\n",
    "        #         dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])\n",
    "        # # print(dp)\n",
    "        # return sum_values - dp[target] - dp[target]\n",
    "        stones = sorted(stones)\n",
    "        sum_values = sum(stones)\n",
    "        n = len(stones)\n",
    "        target = sum_values // 2\n",
    "        dp = [[0] * (target+1) for _ in range(n)]\n",
    "        for j in range(stones[0], target+1):\n",
    "            dp[0][j] = stones[0]\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, target+1):\n",
    "                if stones[i] > j:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i]]+stones[i])\n",
    "        print(dp)\n",
    "        return sum_values - dp[n-1][target] - dp[n-1][target]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        \n",
    "        value = sum(stones)//2+1\n",
    "        objects = len(stones)\n",
    "        dp = [[0]*value for _ in range(objects)]\n",
    "\n",
    "        for j in range(stones[0],value):\n",
    "            dp[0][j] = stones[0]\n",
    "\n",
    "        for i in range(1,objects):\n",
    "            for j in range(1,value):\n",
    "                if stones[i] > j:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-stones[i]]+stones[i])\n",
    "        print(dp)\n",
    "\n",
    "        \n",
    "\n",
    "        return sum(stones) - 2*dp[-1][-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        #尽可能分为两个重量相等的组,使得剩余最小重量最小\n",
    "        sumn=sum(stones)\n",
    "        delsum=sumn//2\n",
    "        n=len(stones)\n",
    "        dp=[[0 for _ in range(delsum+1)] for _ in range(n+1)]\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(delsum+1):\n",
    "                if j<stones[i-1]:\n",
    "                    dp[i][j]=dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-stones[i-1]]+stones[i-1])\n",
    "        print(dp)\n",
    "        res=sumn-2*dp[n][delsum]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        ###### 二分+枚举+贪心 找与target最接近的和\n",
    "        n = len(stones)\n",
    "        tot_sum = sum(stones)\n",
    "        target = tot_sum // 2\n",
    "        #### 二分，枚举所有可能的和\n",
    "        a1 = self.my_enumerate(stones[ : n//2])\n",
    "        a2 = self.my_enumerate(stones[n//2 : ])\n",
    "        a1.sort()       ## 排序，方便下一步贪心\n",
    "        a2.sort()\n",
    "\n",
    "        diff = float('inf')\n",
    "        i, j = 0, len(a2)-1\n",
    "        while i < len(a1) and -1 < j:\n",
    "            cur_sum = a1[i] + a2[j]\n",
    "            if abs(cur_sum - target) < abs(diff):\n",
    "                diff = cur_sum - target\n",
    "            if cur_sum < target:\n",
    "                i += 1\n",
    "            elif cur_sum > target:\n",
    "                j -= 1\n",
    "            else:           #diff都为0了。没有比下去的必要了\n",
    "                break\n",
    "        a = diff + target\n",
    "        b = tot_sum - a\n",
    "        return abs(a - b)\n",
    "\n",
    "    ########### 自定义枚举函数\n",
    "    def my_enumerate(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [0 for _ in range(1 << n)]    # 2**n种情况\n",
    "        for i in range(n):\n",
    "            for j in range(1 << i):\n",
    "                res[(1 << i) + j] = nums[i] + res[j]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        n = len(stones)\n",
    "        target = sum(stones) // 2\n",
    "        dp = [[0 for _ in range(target+1)] for _ in range(n)]\n",
    "        for j in range(target+1):\n",
    "            if stones[0] <= j:\n",
    "                dp[0][j] = stones[0]\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, target+1):\n",
    "                if stones[i] == j:\n",
    "                    dp[i][j] = j\n",
    "                elif stones[i] > j:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-stones[i]] + stones[i])\n",
    "        print(dp)\n",
    "        value = dp[n-1][target]\n",
    "        res = sum(stones) - value - value\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        dp = [0]*150001\n",
    "        target = sum(stones)//2\n",
    "        for stone in stones:\n",
    "            for j in range(target,stone-1,-1):\n",
    "                dp[j] = max(dp[j],dp[j-stone]+stone)\n",
    "        return sum(stones) - 2*dp[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastStoneWeightII(self, stones: List[int]) -> int:\n",
    "        sum1 = sum(stones)//2\n",
    "        print(sum1)\n",
    "        dp = [[0]*(sum1+1) for _ in range(len(stones))]\n",
    "        for i in range(1,sum1+1):\n",
    "            if i>=stones[0]:\n",
    "                dp[0][i] = stones[0]\n",
    "        print(dp)\n",
    "        for i in range(1,len(stones)):\n",
    "            for j in range(1,sum1+1):\n",
    "                if j<stones[i]:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-stones[i]]+stones[i])\n",
    "        \n",
    "                    \n",
    "        print(dp)\n",
    "        print(sum(stones))\n",
    "        return abs(sum(stones)-2*dp[-1][-1])\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
